/*
 * @Description: 
 * @Autor: yanwang
 * @Date: 2021-11-09 15:49:59
 * @LastEditors: yanwang
 * @LastEditTime: 2021-11-09 16:21:14
 */
/*
 * @lc app=leetcode.cn id=208 lang=typescript
 *
 * [208] 实现 Trie (前缀树)
 */

// @lc code=start
class TrieNode {
  flag: boolean;
  next: any[]
  constructor() {
    this.flag = false;
    this.next = [];
  }
}
class Trie {
    root: TrieNode;
    BASE: number;
    constructor() {
      this.root = new TrieNode();
      this.BASE = 26;
    }

    insert(word: string): void {
      let p = this.root;
      for (let i = 0; i < word.length; i++) {
        const x = word[i];
        const ind = x.charCodeAt(0) - 'a'.charCodeAt(0);
        
        if(!p.next[ind]) p.next[ind] = new TrieNode();
        p = p.next[ind];
      }
      p.flag = true;
    }

    search(word: string): boolean {
      let p = this.root;
      for (let i = 0; i < word.length; i++) {
        const x = word[i];
        const ind = x.charCodeAt(0) - 'a'.charCodeAt(0);

        if(!p.next[ind]) return false;
        p = p.next[ind];
      }
      return p.flag;
    }

    startsWith(prefix: string): boolean {
      let p = this.root;
      for (let i = 0; i < prefix.length; i++) {
        const x = prefix[i];
        const ind = x.charCodeAt(0) - 'a'.charCodeAt(0);

        if(!p.next[ind]) return false;
        p = p.next[ind];
      }
      return true;
    }
}

/**
 * Your Trie object will be instantiated and called as such:
 * var obj = new Trie()
 * obj.insert(word)
 * var param_2 = obj.search(word)
 * var param_3 = obj.startsWith(prefix)
 */
// @lc code=end

